// #include <iostream>
// #include <set>
// #include <vector>
// #include <cmath>
// #include <algorithm>
// using namespace std;

// bool is_perfect_square_num(int num)
// {
//     int n = sqrt(num);
//     // cout << "num: " << num << "n : " << n << endl;
//     if (n * n == num)
//         return true;
//     else
//         return false;
// }

// int main()
// {
//     int n;
//     cin >> n;
//     vector<int> v;
//     for (int i = n; i >= 1; i--)
//     {
//         if (is_perfect_square_num(i))
//         {
//             v.push_back(i);
//         }
//     }
//     int len = v.size();
//     int ret = 0;
//     // for(int i = 0; i < len; i++)
//     // {
//     //     cout << v[i] << " ";
//     // }cout << endl;
//     for (int i = 0; i < v.size();)
//     {
//         if (n >= v[i])
//         {
//             // cout << n << " " << v[i] << endl;
//             n -= v[i];
//             ret += 1;
//             if(n == 0) break;
//         }
//         else
//         {
//             i += 1;
//         }
//     }
//     cout << ret;
//     return 0;
// }

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;

#define MAX_N 1000

int dp[MAX_N + 5][MAX_N + 5];

bool is_perfect_square_num(int num)
{
    int n = sqrt(num);
    // cout << "num: " << num << "n : " << n << endl;
    return n * n == num;
}

int main()
{
    int n;
    cin >> n;
    vector<int> use_perfect;
    memset(dp, 0x3f, sizeof dp);
    for (int i = n; i >= 1; i--)
    {
        if (is_perfect_square_num(i))
        {
            use_perfect.push_back(i);
        }
    }
    int ret = 0;
    int len = use_perfect.size();
    dp[0][0] = 0;

    for (int i = 1; i <= len; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j < use_perfect[i - 1]) continue;
            dp[i][j] = min(dp[i][j], dp[i][j - use_perfect[i - 1]] + 1);
        }
    }
    cout << dp[len][n] << endl;
    return 0;
}